In a conventional scheme, when a numerical analysis of a physical phenomenon such as elastic structure analysis, thermal conductance analysis, heat transfer analysis, fluid flow analysis, electrical and magnetic field analysis on a computing machine including products or physical systems is performed by solving a partial differential equation, the finite element method (FEM) is one of the most widely used computer aided engineering tools. Thanks to the advent of large-scale computers, particularly supercomputers, the finite element method has become an extremely effective technique for analyzing phenomena such as large-scale structures or systems. Its range of applications continues to expand.
The FEM method had its beginning as a method for structural analysis, but today it is used in the design and analysis of all kinds of product systems and physical systems.
In terms of the analysis itself, the finite analysis method assumes that a system to be analyzed can be constructed from numerous elements hinging upon many nodes. A system of simultaneous equations discretized for these elements is created and their solution is calculated. For this system of simultaneous equations, the computing time and the memory requirements grow as the number of separate elements increases. Numerous researchers are working to reduce the memory requirements, but despite their efforts, the need for ever larger memory capacity and computing time cannot be avoided.
In an analysis using the FEM method, a two- or three-dimensional region to be drawn for a numerical calculation is divided into small regions called "meshes" or "elements" and linear equations approximately equivalent to partial differential equations are determined on the vertices called "nodes" of each element under the boundary condition. For example, in a set of linear equations that are determined for each node, one element is represented by the following expression which is described by balancing equations, which could represent, for example, an elastic structure analysis, EQU [K.sub.q ].multidot.[U.sub.q ]=[f.sub.q ] (1)
where the subscript "q" shows the qth number of the element; {q=1,2, . . . ,n; n is the total number of elements in an analytical system} and [K.sub.q ] is a constant matrix, [f.sub.q ] is a constant vector determined with the boundary condition on each node and [U.sub.q ] is a vector of unknown variables. Next, by using equation (1), a linear equation for the entire analytical system is obtained with the following equation (2), where [K] is a constant matrix, [f] is a constant vector and [U] is a vector of unknown variables. EQU [K].multidot.[U]=[f] (2)
The solution of linear equation (2) is obtained by generating the inverse matrix [K].sup.-1 of the constant matrix [K] using a general numerical technique of the mathematical method. The result is a solution of the physical phenomenon.
A system of linear equations required to be solved with FEM techniques is often a large and complex structure and computationally difficult to solve because of the limitation of the memory contents and the time imposed on a computer system for processing the large coefficient matrix [K] of equation (2). However, as this large matrix is a sparse matrix, the nonzero elements exist only in a very small percentage of the matrix [K]. Moreover, [K] is a band diagonal matrix. That is, the nonzero elements construct a band diagonal form in all cases.
Many systems and methods for solving equations having sparse and band diagonal matrices that arise in the application of the FEM have been proposed. The methods and systems can be categorized in two groups: the direct method and the iterative method.
The direct method is an analytical technique for solving linear equations. Examples of this method are the Gaussian Elimination Method and the LU Factorization Method which considers only the nonzero elements of the [K] matrix, the Cholesky-band matrix method and the skyline method which uses the characteristic of diagonal band structure of nonzero elements in the matrix [K], the Wave Front method and the Substructure method which decompose a system into a number of subsystems of the same structure. The direct method can generally guarantee a solution with a finite amount of processing.
The iterative method is not an analytical method of solving linear equations. An example of this method is the Conjugate Gradient method which produces an approximated solution within a predetermined error. The iterative method performs iterative calculations on an initial data set to derive a solution within the desired error. Iterative processing does not guarantee to produce the solution in a finite amount of processing.
The direct method has been used as a linear system solver in a Neumann-type computer system using sequential processing, but recently, the iterative method has also been used for solving large linear systems in a parallel processing computational machine for reducing the time and processing required.
Two methods suitable for parallel processing have recently been proposed. One is an analytical solution method called the "parallel structure method" by C. Farhat and E. Wilson and the other is an iterative solution method called the "domain decomposition method."
The parallel substructure method uses the characteristics of two kinds of matrix structures: a border band block form and a diagonal block form, which are called "BBD Matrix." Each form is constructed by decomposing a large system into the boundary elements and the internal elements. In this process, each diagonal block can be processed simultaneously in parallel and the results for each block are substituted in the corresponding boundary border bound block for reducing the original matrix. This reduced matrix has smaller dimensions than the original one and can be solved in a shortened processing time.
The domain decomposition method is an iterative decentralized computational process using two kinds of methods. They are the Normal Direct Method for each domain decomposed and Conjugate Gradient Method for adjusting the boundary conditions of connecting adjacent domains. With these methods, the iterative process of each parallel processing is processed until a mismatch of the calculated solution error enters into the range of a limited value. However, when an analysis for a larger system is performed, in spite of parallel processing realized by such high-level computations systems as a pipeline and a parallel multiprocessor having a high speed of execution, the computational systems become impractical and inefficient. This is because the iterative processing time and the connective size between domains increase as a function of system structure.